//
//  StringMatching.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2021/1/5.
//

import Foundation

class StringMatching: NSObject {
    
//    static let alphabetValues:[String: Int64] = ["a":1,"b":26,"c":52,"d":104,"e":208,"f":416,"g":832,"h":1664,"i":3328,"j":6656,"k":13312,"l":26624,"m":53248,"n":106496,"o":212992,"p":425984,"q":851968,"r":1703936,"s":3407872,"t":6815744,"u":13631488,"v":27262976,"w":54525952,"x":109051904,"y":218103808,"z":436207616]
    static let alphabetValues:[String: Int64] = ["a":1,"b":2,"c":3,"d":4,"e":5,"f":6,"g":7,"h":8,"i":9,"j":10,"k":11,"l":12,"m":13,"n":14,"o":15,"p":16,"q":17,"r":18,"s":19,"t":20,"u":21,"v":22,"w":23,"x":24,"y":25,"z":26]
    
    static var n26arr: [Int64]?
    /// 字符串匹配之BF算法
    /// - Parameters:
    ///   - hostString: 主串，即去哪个字符串中查
    ///   - patternString: 模式串，即要查那一串
    /// - Returns:返回查询结果，查到了返回true
    class func bruteForce(_ hostString: String, patternString:String) -> Bool {
        let n = hostString.count
        let m = patternString.count
        if n < m {
            return false
        }
        
        for i in 0..<n - m{
            // 获取子串
            let startIndex = hostString.index(hostString.startIndex, offsetBy: i)
            let endIndex = hostString.index(startIndex, offsetBy: m - 1)
            let tempString = hostString[startIndex...endIndex]
            
            // 比较子串和模式串
            if compare(firstString: String(tempString), secondString: patternString) {
                return true
            }
        }
        return false
    }
    
    /// 二维矩阵匹配
    /// - Parameters:
    ///   - hostArrs: 主二维矩阵
    ///   - patternArr: 模式二维矩阵
    /// - Returns: 返回查找结果
    class func bruteForceTwoDimensional(_ hostArrs:[[String]],patternArr: [[String]]) -> Bool {
        let patternXCount = patternArr.count
        let patternYCount = patternArr.first!.count
        let hostXCount = hostArrs.count
        let hostYCount = hostArrs.first!.count
        for i in 0...hostXCount - patternXCount {
            for j in 0...hostYCount  - patternYCount{
                // 获取子二维数组
                let subArr = getSubArrs(hostArrs, startXIndex: i, startYIndex: j, xCount: patternXCount, yCount: patternYCount)
                // 比较子二维数组与模式二维数组
                if subArr == patternArr {
                    return true
                }
            }
        }
        return false
        
    }
    
    
    /// 字符串匹配之-RK算法
    /// - Parameters:
    ///   - hostString: 主串，即去哪个字符串中查
    ///   - patternString: 模式串，即在那一串字符中查
    /// - Returns: 返回查询结果，查到返回true
    class func rabinKarp(_ hostString: String, patternString: String) -> Bool {
        let n = hostString.count
        let m = patternString.count
        if n < m {
            return false
        }
        // 模式串的哈希值
        let patternValue = customHashValue(patternString)
//        let patternValue = patternString.hashValue

//        // 获取主串中第一个子串的哈希值
//        let endIndex = hostString.index(hostString.startIndex, offsetBy: m - 1)
//        let firstString = hostString[hostString.startIndex...endIndex]
//        var firstValue = hashValue(String(firstString))
//
//        // 第一个字串相等的情况
//        if patternValue == firstValue {
//            if String(firstString) == patternString{
//                return true
//            }
//        }
//        let firstChar = String(hostString[hostString.startIndex])
//        var firsCharValue: Int64 = alphabetValues[firstChar]!
//        for i in 1..<n - m{
//            // 获取最后一个字母的值
//            let lastIndex = hostString.index(hostString.startIndex, offsetBy: m - 1 + i)
//            let lastCase = String(hostString[lastIndex])
//            let lastValue = alphabetValues[String(lastCase)]!
//
//            // 得出子串哈希值
//            let sonValue = firstValue - firsCharValue + lastValue
//
//            // 记录第一个字母的值
//            let firstIndex = hostString.index(hostString.startIndex, offsetBy: i)
//            let firstCase = String(hostString[firstIndex])
//            firsCharValue = alphabetValues[firstCase]!
//
//            if sonValue == patternValue {
//                let sonString = String(hostString[firstIndex...lastIndex])
//                if compare(firstString: String(sonString), secondString: patternString) {
//                    return true
//                }
//            }
//            // 记录此次子串的哈希值，作为下次比较的初始值
//            firstValue = sonValue
//        }
        for i in 0..<n - m{
            // 获取子串
            let firstIndex = hostString.index(hostString.startIndex, offsetBy: i)
            let endIndex = hostString.index(firstIndex, offsetBy: m - 1)
            let subString = String(hostString[firstIndex...endIndex])
            // 计算子串的哈希值
            let sonHashValue = customHashValue(subString)
//            let sonHashValue = subString.hashValue

            if sonHashValue == patternValue {
                if compare(firstString: subString, secondString: patternString) {
                    return true
                }
            }
        }
        return false
    }
    
    // 字符串匹配之KMP算法
    class func kmp(_ hostString: String, patternString: String) -> Int {
        let m = patternString.count
        // 创建模式串的next数组
        let nextArr = getNexts(patternString)
        var j = 0
        for (i,char) in hostString.enumerated() {
            while j > 0 && String(patternString[patternString.index(patternString.startIndex, offsetBy: j)]) != String(char) {
                // 当碰到坏字符，取好前缀的最长匹配后缀的末尾字符下标，然后往后移一位开始继续匹配
                j = nextArr[j - 1] + 1
            }
            
            if String(patternString[patternString.index(patternString.startIndex, offsetBy: j)]) == String(char) {
                j += 1
            }
            
            if j == m {
                return i - m + 1
            }
            
        }
        
        return -1
    }
    
    
}

extension StringMatching{
    
    /// 根据字符串获取哈希值
    /// - Parameter string: 要转换的字符串
    /// - Returns: 返回哈希值
    class func customHashValue(_ string: String) -> Int64 {
        var sum: Int64 = 0
        for i in string.indices {
            sum = sum + alphabetValues[String(string[i])]!
        }
        return sum
    }
    
    class func compare(firstString string1: String, secondString string2: String) -> Bool{
        let count = string1.count
        if count != string2.count{
            return false
        }
        
        for i in string1.indices {
            
            if string1[i] != string2[i] {
                return false
            }
        }
        return true
    }
    
    class func get26nArrs(nCount n:Int) -> [Int64]{
        var arr = [Int64](repeating: 0, count: n)
        for i in 0..<n {
            if i == 0 {
                arr[i] = 1
            }else{
                arr[i] = arr[i - 1] * 5
            }
        }
        return arr
    }
    
    class func getSubArrs(_ hostArrs: [[String]], startXIndex xIndex: Int, startYIndex yIndex: Int, xCount: Int, yCount: Int) -> [[String]]{
        var resultArrs = [[String]](repeating: [String](repeating: "", count: xCount), count: yCount)
        for i in 0..<xCount {
            for j in 0..<yCount {
                resultArrs[i][j] = hostArrs[i + xIndex][j + yIndex]
            }
        }
        return resultArrs
    }
    
    class func getNexts(_ patternString: String) -> [Int]{
        let m = patternString.count
        var nexts = [Int](repeating: -1, count: m)
        var k = -1
        for (i, char) in patternString.enumerated() {
            if i == 0 {
                continue
            }
            
            while k != -1 && String(patternString[patternString.index(patternString.startIndex, offsetBy: k + 1)]) != String(char){
                k = nexts[k]
            }
            
            if String(patternString[patternString.index(patternString.startIndex, offsetBy: k + 1)]) == String(char) {
                k += 1
            }
            nexts[i] = k
        }
        return nexts
    }
}
